%!TEX program = xelatex

\documentclass[UTF8]{article}
\author {sjzez czy}
\title {一类通过生成函数求线性递推式的方法}
\date{2019.1.22}
\usepackage[UTF8]{ctex}
\usepackage{listings}
\usepackage{fontspec}
\usepackage{ctex}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\usepackage{setspace}
\usepackage{abstract}
\usepackage{graphicx}
\setmonofont{Consolas}
\usepackage[colorlinks,linkcolor=black,citecolor=black]{hyperref}
\renewcommand{\baselinestretch}{1.5}
\geometry{a4paper,left=2.7cm,right=2.7cm,top=2.7cm,bottom=2.7cm}


\begin{document}

\maketitle

\begin{abstract}
    在一类低阶卷积递推中，常用方法是多项式开根来优化递推，但在某些特殊情况下，可以实现递推来求解，使得时间复杂度变为线性
    \newline
    \centering
    \textbf{关键字：} 卷积、形式幂级数、生成函数、多项式开根
\end{abstract}

\newpage
\tableofcontents

\newpage

\section{定义}

\subsection{卷积}

对于一个矩阵 $\{a_{n,m}\}$，定义其 $n$ 阶卷积 $\{c_k\}$ 为：

$$
c_k=\sum_{\sum_{j=1}^{n}p_j=k}\prod_{i=1}^{n} a_{i,p_i}
$$

\subsection{卷积递推}

定义一个序列 $\{f_k\}$ 是关于 $g_k,h_k,\{a_{u,v}\}$ 的 $u$ 阶卷积递推，意味着：

$$
f_k=g_k+h_k\sum_{\sum_{j=1}^{u}p_j=k}\prod_{i=1}^{u}a_{i,p_i}
$$

\subsection{形式幂级数}

对于一个序列 $\{a_n\}$，定义它的形式幂级数 $A(x)$ 为：

$$
A(x)=\sum_{n=0}^{\infty}a_nx^n
$$

在这里，并不关注 $x$ 的取值，只是用它的一个形式，但如果将其转化为封闭形式后，需要保证 $a_0=A(0)$ 成立

在本文中，不加区分形式幂级数与生成函数的区别，形式幂级数拥有一些常见的算术运算方式

\subsubsection{相等}

定义 $A(x)=B(x)$，意味着：

$$
\forall n \ge 0,a_n=b_n
$$

\subsubsection{加法}

定义 $C(x)=A(x)+B(x)$，意味着：

$$
\sum_{n=0}^{\infty}c_nx^n=\sum_{n=0}^{\infty}(a_n+b_n)x^n
$$

\subsubsection{乘法}

定义 $C(x)=A(x) \times B(x)$，意味着：

$$
\sum_{n=0}^{\infty}c_nx^n=\sum_{n=0}^{\infty}x^n \sum_{i+j=n} a_i \times b_j
$$

\section{引理}

\subsection{形式幂级数的导数}

由于 $x^n$ 的导数为 $nx^{n-1}$，由此可得对于形式幂级数 $A(x)$ 来说，它的导数为：

$$
A ^\prime (x)=\sum_{n=0}^{\infty} a_{n+1}(n+1)x^n
$$

同时可以得知，如果已知 $F(0)$ 和 $F ^\prime (x)$，可以还原出 $F(x)$

\subsection{形式幂级数的幂次}

通过形式幂级数的导数，可以得出如下结论：

$$
\begin{aligned}
    & F(x)=A(x)^{p} \\
    \Rightarrow & F ^\prime (x)=pA(x)^{p-1}A ^\prime (x) \\
    \Rightarrow & A(x)F ^\prime (x)=pA(x)^pA ^\prime (x) \\
    \Rightarrow & A(x)F ^\prime (x)=pF(x)A ^\prime (x)
\end{aligned}
$$

\section{实例}

\subsection{Large Schröder numbers}

已知 \textbf{Large Schröder numbers} 的形式幂级数为 $F(x)=\frac{1-x-\sqrt{1-6x^+x^2}}{2x}$，求其递推式

设 $G(x)=\sqrt{1-6x+x^2}$

\subsubsection{求 $G(x)$}

因为：

$$
\begin{aligned}
&(1-6x+x^2)G'(x)=\frac{1}{2}G(x)(1-6x+x^2)' \\
\Rightarrow &(1-6x+x^2)G'(x)=G(x)(x-3) \\
\Rightarrow &\sum_{n=0}^{\infty}g_{n+1}(n+1)x^{n}-\sum_{n=1}^{\infty}6g_{n}nx^n+\sum_{n=2}^{\infty}g_{n-1}(n-1)x^n=\sum_{n=1}^{\infty}g_{n-1}x^n-\sum_{n=0}^{\infty} 3g_nx^n
\end{aligned}
$$

于是有：

$$
\begin{cases}
g_0=G(0)=1 \\
g_{0+1}(0+1)=-3g_0 \\
g_{1+1}(1+1)-6g_11=g_{1-1}-3g_1 \\
g_{n+1}(n+1)-6g_nn+g_{n-1}(n-1)=g_{n-1}-3g_n \quad (n \ge 2)
\end{cases}
$$

那么：

\textbf{初值}

$$
\begin{cases}
g_0=1 \\
g_1=-3g_0=-3 \\
2g_2-6g_1=g_0-3g_1 \Rightarrow g_2=-4
\end{cases}
$$

\textbf{其它情况}

$$
\begin{aligned}
&g_{n+1}(n+1)+(3-6n)g_n+g_{n-1}(n-2)=0 \quad & (n \ge 2) \\
\Rightarrow &g_{n+1}=\frac{(6n-3)g_n+g_{n-1}(2-n)}{n+1} \quad & (n \ge 2) \\
\Rightarrow &g_{n}=\frac{(6n-9)g_{n-1}+(3-n)g_{n-2}}{n} \quad & (n \ge 1)
\end{aligned}
$$

\subsubsection{求 $F(x)$}

因为 $2xF(x)=1-x-G(x)$，则有：

$$
\sum_{n=1}^{\infty}2f_{n-1}x^n=1-x-g_0-g_1x-\sum_{n=2}^{\infty}g_nx^n
$$

那么：

\textbf{初值}

$$
2f_{1-1}=-1-g_1 \Rightarrow f_0=1
$$

\textbf{其它情况}

$$
\begin{aligned}
&2f_{n-1}=-g_n \quad &(n \ge 2) \\
\Rightarrow &f_{n}=-\frac{g_{n+1}}{2} \quad & (n \ge 1)
\end{aligned}
$$

\subsection{Motzkin numbers}

已知 \textbf{Motzkin numbers} 的形式幂级数为 $F(x)=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}$，求其递推式

设 $G(x)=\sqrt{1-2x-3x^2}$

\subsubsection{求 $G(x)$}

$$
\begin{aligned}
&G(x)=\sqrt{1-2x-3x^2} \\
\Rightarrow &(1-2x-3x^2)G'(x)=\frac{1}{2}G(x)(-2-6x) \\
\Rightarrow &(-1+2x+3x^2)G'(x)=(1+3x)G(x) \\
\Rightarrow &(-1+2x+3x^2)\sum_{n=0}^{\infty}g_{n+1}(n+1)x^n=(1+3x)\sum_{n=0}^{\infty}g_nx^n \\
\Rightarrow &-\sum_{n=0}^{\infty}g_{n+1}(n+1)x^n+\sum_{n=1}^{\infty}2g_{n}nx^n+\sum_{n=2}^{\infty}3g_{n-1}(n-1)x^n=\sum_{n=0}^{\infty}g_nx^n+\sum_{n=1}^{\infty}3g_{n-1}x^n \\
\end{aligned}
$$

可以得出：

$$
\begin{cases}
g_0=G(0)=1 \\
-g_{0+1}(0+1)=g_0 \Rightarrow g_1=-1 \\
-g_{1+1}(1+1)+2g_11=g_1+3g_{1-1} \Rightarrow g_2=-2 \\
-g_{n+1}(n+1)+2g_nn+3g_{n-1}(n-1)=g_{n}+3g_{n-1} \quad & (n \ge 2)\\
\end{cases}
$$

最后一个即：

$$
\begin{aligned}
&-g_{n+1}(n+1)+2g_nn+3g_{n-1}(n-1)=g_{n}+3g_{n-1} \quad & (n \ge 2) \\
\Rightarrow &-g_{n+1}(n+1)+(2n-1)g_n+(3n-6)g_{n-1}=0 \quad & (n \ge 2) \\
\Rightarrow &g_n=\frac{(2n-3)g_{n-1}+(3n-9)g_{n-2}}{n} \quad & (n \ge 3) \\
\end{aligned}
$$

\subsubsection{求 $F(x)$}

因为：

$$
\begin{aligned}
&2x^2F(x)=1-x-G(x) \\
\Rightarrow &\sum_{n=2}^{\infty}2f_{n-2}x^n=(1-g_0)-(g_1+1)x-\sum_{n=2}^{\infty}g_nx^n
\end{aligned}
$$

可以得出：

$$
\begin{aligned}
&2f_{n-2}=-g_n \quad & (n \ge 2) \\
\Rightarrow &f_{n}=-\frac{g_{n+2}}{2} \quad & (n \ge 0)
\end{aligned}
$$

\subsection{Catalan numbers}

已知 \textbf{Catalan numbers} 的形式幂级数为 $F(x)=\frac{1-\sqrt{1-4x}}{2x}$，求其递推式

设 $G(x)=\sqrt{1-4x}$

\subsubsection{求 $G(x)$}

$$
\begin{aligned}
&G(x)=\sqrt{1-4x} \\
\Rightarrow &(1-4x)G'(x)=\frac{1}{2}G(x)(-4) \\
\Rightarrow &(4x-1)\sum_{n=0}^{\infty}g_{n+1}(n+1)x^n=\sum_{n=0}^{\infty}2g_nx^n \\
\Rightarrow &\sum_{n=1}^{\infty}4g_{n}nx^n-\sum_{n=0}^{\infty}g_{n+1}(n+1)x^n=\sum_{n=0}^{\infty}2g_nx^n \\
\end{aligned}
$$

可以得出：

$$
\begin{cases}
g_0=G(0)=1 \\
-g_{0+1}(0+1)=2g_0 \Rightarrow g_1=-2 \\
4g_{n}n-g_{n+1}(n+1)=2g_{n} \quad (n \ge 1)
\end{cases}
$$

最后一个即：

$$
\begin{aligned}
&4g_nn-g_{n+1}(n+1)=2g_n \quad & (n \ge 1) \\
\Rightarrow &g_{n+1}=\frac{(4n-2)g_n}{n+1} \quad & (n \ge 1) \\
\Rightarrow &g_{n}=\frac{(4n-6)g_{n-1}}{n} \quad & (n \ge 2) \\
\end{aligned}
$$

\subsubsection{求 $F(x)$}

因为：

$$
\begin{aligned}
&2xF(x)=1-G(x) \\
\Rightarrow & \sum_{n=1}^{\infty}2f_{n-1}x^n=1-\sum_{n=0}^{\infty} g_{nx^n}
\end{aligned}
$$

可以得出：

$$
\begin{aligned}
&2f_{n-1}=-g_{n} \quad & (n \ge 1) \\
\Rightarrow & f_{n}=-\frac{g_{n+1}}{2} \quad & (n \ge 0)
\end{aligned}
$$

\begin{thebibliography}{}
    \bibitem[1]{REF1}\href{https://zhuanlan.zhihu.com/p/31457805}{生成函数及应用}, ACdreamer
    \bibitem[2]{REF2}\href{https://zhuanlan.zhihu.com/p/54318231}{迷思：寻找母函数运算的组合意义（一）}, EntropyIncreaser
\end{thebibliography}

\end{document}
